#include <iostream>
#include <queue>

using namespace std;

template<typename T>
class BST {
private:
  struct BSTNode {
    T _data;
    BSTNode* _left;
    BSTNode* _right;

    BSTNode(T value) : _data(value), _left(NULL), _right(NULL) {}
  };

public:
  BST() : _root(NULL) {}

  void insert(T val) {
    _root = insert_rec(_root, val);
  }

  void inorder(ostream& os) const {
    inorder_rec(os, _root);
  }
  
  void preorder(ostream& os) const {
    preorder_rec(os, _root);
  }

  void postorder(ostream& os) const {
    postorder_rec(os, _root);
  }

  void levelorder(ostream& os) const {
    queue<BSTNode*> q;
    if (_root)
      q.push(_root);

    while (!q.empty()) {
      BSTNode* cur = q.front(); q.pop();
      os << cur->_data << " ";
      if (cur->_left) q.push(cur->_left);
      if (cur->_right) q.push(cur->_right);
    }
  }

  // print out the smallest k numbers
  void least_k(ostream& os, size_t k) {
    least_k_rec(os, _root, k);
  }

  // mirror the tree. after this, it's not bst any more
  void reverse() {
    reverse_rec(_root);
  }

private:
  BSTNode* _root;

  BST(const BST&);
  BST& operator=(const BST&);

  void reverse_rec(BSTNode* root) {
    if (!root) return;
    reverse_rec(root->_left);
    reverse_rec(root->_right);

    swap(root->_left, root->_right);
  }

  void least_k_rec(ostream& os, BSTNode* root, size_t& cnt) {
    if (root && cnt > 0) {
      least_k_rec(os, root->_left, cnt);
      if (cnt > 0) {
	os << root->_data << " ";
	cnt--;
      }
      least_k_rec(os, root->_right, cnt);
    }
  }

  BSTNode* find(BSTNode* root, const T& val) const {
    if (root) {
      if (root->_data == val)
	return root;
      if (root->_data > val)
	return find(root->_left, val);
      else
	return find(root->_right, val);
    }
    return NULL;
  }

  void postorder_rec(ostream& os, BSTNode* root) const {
    if (root) {
      postorder_rec(os, root->_left);
      postorder_rec(os, root->_right);
      os << root->_data << " ";
    }
  }

  void preorder_rec(ostream& os, BSTNode* root) const {
    if (root) {
      os << root->_data << " ";
      preorder_rec(os, root->_left);
      preorder_rec(os, root->_right);
    }
  }

  void inorder_rec(ostream& os, BSTNode* root) const {
    if (root) {
      inorder_rec(os, root->_left);
      os << root->_data << " ";
      inorder_rec(os, root->_right);
    }
  }

  BSTNode* insert_rec(BSTNode* p, T val) {
    if (!p) {
      return new BSTNode(val);
    }
    if (p->_data > val) {
      p->_left = insert_rec(p->_left, val);
    }
    else {
      p->_right = insert_rec(p->_right, val);
    }
    return p;
  }
};

// problem 4

int main() {
  BST<int> t; 
  t.insert(5); t.insert(3); t.insert(1); t.insert(4);
  t.insert(8); t.insert(6); t.insert(7);

  cout << "Test BST inorder" << endl;
  t.inorder(cout); cout << endl;

  cout << "Test BST preorder" << endl;
  t.preorder(cout); cout << endl;

  cout << "Test BST postorder" << endl;
  t.postorder(cout); cout << endl;

  cout << "Test level order" << endl;
  t.levelorder(cout); cout << endl;

  cout << "Test least k numbers" << endl;
  t.least_k(cout, 5); cout << endl;

  cout << "Test mirror tree" << endl;
  t.reverse(); 
  cout << "Preorder: "; t.preorder(cout); cout << endl;
  cout << "Inorder: "; t.inorder(cout); cout << endl;
  cout << "Postorder: "; t.postorder(cout); cout << endl;
  cout << "Levelorder: "; t.levelorder(cout); cout << endl;

  return 0;
}
